#include <stdio.h>
#include <string.h>
#include <stdlib.h>

#define MAXLINES 5000
#define MAXLEN 1000

char* lineptr[MAXLINES];

int readlines(char* lineptr[], int nlines);
void writelines(char* lineptr[], int nlines);
void qsort(char* lineptr[], int left, int right);
int getline(char*);
void swap(char* [], int, int);

int main() {
	int nlines;

	if ((nlines = readlines(lineptr, MAXLINES)) >= 0) {
		qsort(lineptr, 0, nlines - 1);
		writelines(lineptr, nlines);
	}
	else {
		printf("error: input tooo big to sort\n");
		return -1;
	}

	return 0;
}

int getline(char* line) {
	int len = 0, c;

	while ((c = getchar()) != '\n' && len < MAXLEN)
	{
		*(line + len) = c;
		len++;
	}
	*(line + len) = '\0';
	return len;
}

void swap(char* linepstr[], int i, int j) {
	char* tmp;

	tmp = lineptr[i];
	lineptr[i] = linepstr[j];
	linepstr[j] = tmp;
}

int readlines(char* lineptr[], int maxlines) {
	int len, nlines;
	char* p, line[MAXLEN];

	nlines = 0;
	while ((len = getline(line)) > 0) {
		if (maxlines <= nlines || (p = (char*)malloc(MAXLEN)) == NULL) {
			return -1;
		}
		else {
			strcpy_s(p, MAXLEN, line);
			lineptr[nlines++] = p;
		}
	}
	return nlines;
}

void writelines(char* lineptr[], int nlines) {
	int i;

	for (i = 0; i < nlines; i++) {
		printf("%s\n", lineptr[i]);
	}
}

void qsort(char* lineptr[], int left, int right) {
	int i, last;

	if (left >= right) return;
	swap(lineptr, left, (left + right) / 2);
	last = left;
	for (i = left + 1; i <= right;i++) {
		if (strcmp(lineptr[i], lineptr[left]) < 0) {
			swap(lineptr, ++last, i);
		}
	}
	swap(lineptr, left, last);
	qsort(lineptr, left, last - 1);
	qsort(lineptr, last + 1, right);
}